package lib

import "sort"

func init() {
	Probs = append(Probs, Problem{
		Num:         611,
		Discription: "有效三角形个数",
		Level:       2,
		Labels: map[string]int{
			"二分查找": 1,
			"排序":   1,
			"贪心":   1,
		},
	})
}

func TriangleNumber(nums []int) (ans int) {
	n := len(nums)
	sort.Ints(nums)
	for i, v := range nums {
		k := i
		for j := i + 1; j < n; j++ {
			for k+1 < n && nums[k+1] < v+nums[j] {
				k++
			}
			ans += max(k-j, 0)
		}
	}
	return
}

/* func triangleNumber(nums []int) (ans int) {
	sort.Ints(nums)
	n := len(nums)
	count := 0

	for i := 0; i < n-2; i++ {
		start := i + 2
		for j := i + 1; j < n-1; j++ {
			if start == n {
				count += n - 1 - j
				continue
			}

			start = max(j+1, start)
			target := nums[i] + nums[j]
			left, right := start, n-1
			for left <= right {
				mid := left + (right-left)/2
				if nums[mid] < target {
					left = mid + 1
				} else {
					right = mid - 1
				}
			}

			if left == n || nums[left] >= target {
				left--
			}

			start = left + 1
			count += left - j
		}
	}

	return count
}
*/
